package simple;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/5/13 19:59
 */
public class No509_斐波那契数 {
    public static void main(String[] args) {
        Solution509 solution509 = new Solution509();
        int fib = solution509.fib(8);
        System.out.println(fib);
    }   
}

class Solution509 {
    public int fib(int n) {
        //通项公式!!!
        //搞出来!!!
        //直接公式代入
        double g5 = Math.sqrt(5);

        double x1 = (1 + g5) / 2;
        double x2 = (1 - g5) / 2;

        return (int) (1 / g5 * (Math.pow(x1, n) - Math.pow(x2, n)));
    }
}



    //public int fib(int n) {
    //    //空间优化
    //    int a = 0;
    //    int b = 1;
    //    int c = a + b; //c肯定最少是第n=2的数了
    //    for (int i = 2; i <= n; i++) {
    //        c = a + b;
    //        a = b;
    //        b = c;
    //    }
    //
    //    return n <= 1 ? n : c;
    //}



    //public int fib(int n) {
    //    if (n == 0) {
    //        return 0;
    //    }
    //    //动态规划
    //    int[] f = new int[n + 1];
    //    //结束条件
    //    f[0] = 0;
    //    f[1] = 1; //注意问题,如果n=0,会报错
    //    
    //    //开始使用递归方程计算f[2],f[3]...f[n]
    //    for (int i = 2; i <= n; i++) {
    //        f[i] = f[i - 1] + f[i - 2];
    //    }
    //    return f[n];
    //}








